package 字符串.middle;

/**
 * @author Lw中
 * @date 2020/9/9 10:32
 */
public class Wu {

    /**
     * LWZ TODO : 2020/9/9
     * 如何存储最长回文子串
     */

    /**
     * 最长回文子串
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s.equals("")) {
            return "";
        }
        String origin = s;
        // 将字符串反转
        String s1 = new StringBuffer(s).reverse().toString();
        int length = origin.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == s1.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        // 保存的就是公共子串的长度
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    int beforeRev = length - 1 - j;
                    //判断下标是否对应
                    if (beforeRev + arr[i][j] - 1 == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }

    public static void main(String[] args) {
        String s = longestPalindrome("cabad");
        System.out.println(s);
    }

}
